#include <iostream>
#include <numeric>
#include <vector>
using namespace std;

bool helper(vector<int>& nums, int now, vector<int>& sums, int avg)
{
    if (now == nums.size()) {
	return true;
    }
    for (int i = 0; i < sums.size(); ++i) {
	if (sums[i] + nums[now] <= avg) {
	    sums[i] = nums[now] + sums[i];
	    bool temp2 = helper(nums, now + 1, sums, avg);
	    if (temp2 == true) {
		return true;
	    }
	    sums[i] = sums[i] - nums[now];
	}
	//如果出现放这个元素导致没有合适的结果，那么剩下的那个也没有必要再试了。
	if (sums[i] == 0) {
	    cout << "0: " << now << endl;
	}
    }
    return false;
}

bool canPartitionKSubsets(vector<int>& nums, int k)
{
    int sumsval = accumulate(nums.begin(), nums.end(), 0);
    if (sumsval % k != 0) {
	//不能被均分
	return false;
    }
    int avg = sumsval / k;
    vector<int> sums;
    sums.resize(k);
    return helper(nums, 0, sums, avg);
}

void proc(vector<int>& nums, int now, int temp, int tar, int& tempres)
{
    if (now == nums.size()) {
	if (tar - temp < tar - tempres) {
	    tempres = temp;
	}
	return;
    }
    proc(nums, now + 1, temp, tar, tempres);
    if (nums[now] + temp <= tar) {
	proc(nums, now + 1, temp + nums[now], tar, tempres);
    }
}

bool canPartition(vector<int>& nums)
{
    int sumsval = accumulate(nums.begin(), nums.end(), 0);
    if((sumsval % 2) != 0)
    {
	return false;
    }
    int restemp = 0;
    proc(nums, 0, 0, sumsval/2,restemp);
    if(restemp != (sumsval /2))
    {
	    return false;
    }
    return true;
}

int main()
{
    vector<int> a = { 354, 1983, 167, 2655, 73, 927, 470, 485, 1035, 405, 1358, 1944, 3404, 4078, 2500, 577 };
    cout << canPartitionKSubsets(a, 5) << endl;
}
